# Full text of "General theory of most efficient codes"

## See other formats

```"LI E> HAHY

OF THE
UNIVERSITY
OF ILLINOIS

510.84

I26T

no. 156-163

cop 2

Digitized by the Internet Archive
in 2013

http://archive.org/details/generaltheoryofm163koma

fC\ S4- DIGITAL COMJ'U'PKK LABORATORY

^ ^ "*" UNIVERSITY OF ILLINOIS

^p ^ URBANA, ILLINOIS

REPORT NO. 163

GENERAL THEORY OF MOST EFFICIENT CODES

by
Yasuo Komamiya

June 9, 196^

The person charging this material is re-
sponsible for its return on or before the
Latest Date stamped below.

Theft, mutilation, and underlining of books
are reasons for disciplinary action and may
result in dismissal from the University.

University of Illinois Library

ACKNOWLEDGMENT

The author wishes to thank Professor David E. Muller for a number of
helpful discussions in connection with this report, and Mrs. Phyllis Olson for
her skillful typing of this paper.

Page

1. INTRODUCTION

2. A THEOREM WHICH PLAYS AN IMPORTANT ROLE IN THE CODING PROBLEM . . 3

3. GENERAL THEORY OF MOST EFFICIENT CODES L3

k. CALCULATION AND SOME PROPERTIES OF EACH \ 28

l

5. SOME PROPERTIES OF C, 37

6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6) 51

7. SOLUTION OF EQ. (3-25) "VA'V T = 0" UNDER CONDITION 6.1 AND

CONDITION 6.2 70

8. GENERAL SOLUTION OF VA' V T = 91

9. GENERAL SOLUTION OF VA' V T = IN APPLICATION OF BOOLEAN ALGEBRA . 101
10. CONCLUSION . 106

•in-

1 . I NTKODUCTION

In this paper, the number of most efficient binary codes and the
construction methods are discussed in general, where the most efficient binaj
codes mean codes with a minimum Hamming distance of p.

The most efficient binary codes are defined mathematically as follows

M(n,p) =

11, X 12' x 13'

x^. , x

L ln

x 21 , x 22 , x 23 , ..., x 2n

, x.

31' 32' 33' "" 3n

(1.1)

X -i » X„, X _, • . • , X

, ml m2 m3 mn.

Consider the matrix M(n,p), where (x.,iX.„,...,x. ) for 1 < i < m

ll i2 in — —

is an n digit binary code. Accordingly, x. . is 1 or and m is the number of

■^- J

most efficient binary codes. Here

x., - x . , + x . ^ - x . ^ + . . . + x. -x. >p for any i f j; 1 < i, j <
ll jl 1 ' i2 j2' ' in jn 1 - ^ J r d ' - ' J -

m

where p is the minimum Hamming distance.

The purpose of this paper is to obtain maximum m and the value of

each x. . .
ij

In Section 2, a theorem which plays an important role in the coding
problem is discussed.

In Section 3> the matrix H(n, p) (by which the coding problem can be
discussed in general) is introduced, and general theory discussed. As a result,
the coding problem is reduced to the problem of determining the independence of
some vectors.

In Section k, the characteristic values of H(n,p) are discussed.

In Sections 5 and 6, some properties of the independence of vectors
are discussed.

In Section 7> solution under some conditions (group code condition
implies these conditions; accordingly, group code is a special case of these
conditions) is discussed.

In Section 8, one method of general solution is discussed.

In Section 9> Boolean algebra is used in finding a general solution,

The c onclusion is stated in Section 10.

2. A THEOREM WHICH PLAY J AN IMPORTANT ROLE IN THE CODJN') PROBL

In this section a theorem which piays an important role in the coding
problem is first described, followed by a discussion of a second, related
theorem.

Definition 2.1 . Exclusive-OR operation "©" between any non-negative integers.

Let a, b be non-negative integers. Define a © b as follows: when
a and b are expanded to binary form, i.e.,

a = a2 + a .,2 + . . . + a, 2 + a_
n n-1 1

b = b 2 n + b ,2 n_1 + ... + b-,2 + b_ ,
n n-1 1

n-1

a © b = (a © b )2 + (a , © b , )2 + . . . + (a, © b, )2 + (a_ © b,J .
n n n-1 n-1 1 1

Here the symbol "©" of the right-hand side of the above formula is an exclusive-
or operation in the usual meaning.

Theorem 2.1. Let z~, z. , .... z , be real numbers. Consider the matrix
7 1 n-1

Z =
n

V V V ■"" Z N-1

'l' V z 3' '"' z l©(N-l)

Z N-1' Z N-2' Z N-3' ""' Z

where N = 2 and n > 1,

-k-

The matrix Z can be transformed to the diagonal matrix by the

orthogonal matrix as follows

where

Z = U AU
n n n

1, 1

Un V N \l, -I*

'1, 1

l1, "I,

X . . . X

'1, 1'

a, -i-

- (u ,u i; •••* u (n_ 1 )-)

and

A =

: (N-1),

Here, the symbol "x" means the direct product (Kronecker's product) and

i, i\ A, i

i, i

k i, -I.

X \ I X ... X

^1, -1/ \h -1

'1. 1

means the n direct products of

The following relations can also be obtained

1, "I

x. = -A (vV-"' z (n-i) )u i

z i ■ ^ (x O' X l'"" X (N-l) )u i

for any i, where < i < (N - 1).

-5-

Proof. Since the matrix Z is a symmetric real matrix, Z can be transformed
n n

to a diagonal matrix by an orthogonal matrix. When n ■ 1, Z, , U, are

z - ■ V Zl
V z o

u ^vtC-J = (u °' Ul)

respectively. The relation

u ( X ° ° ) u = -± ( lr ) ( X ° ° ) -i I 1 ' ) = i f X ° + Xl ' X ° ' Xl

1 \0 x 1 / X ^2 \1, -1/ \0 x 1 /^2 \1, -1/ 2 \x - x x , x Q + Xl

holds. Therefore, letting

z Q = | (x Q + xj_) = \ (x Q ,x 1 ) f j = j (x ,x 1 )u

z i = I (x o - x i } = \ ( V x i } (J = ^ ( V x i )u i'

the relations

x Q = z Q + z ± = (z , Zl ) ( ^ j = nT 2 (z , Zl )u

x i = z o - z i = ( V z i } (^J = ^ ( V z i )u i

can he obtained. Therefore, the theorem holds for n = 1.

Now suppose that xhe theorem holds for n, then it may be proved by
mathematical induction that the theorem also holds for (n + l).

It is possible to let

-6-

n+l

x , x 1

X l' x o

where

and

X = Z
n

X l =

V Z N+1' "••' Z 2N-1

. N+1 , z N , . .., z le ( 2N _-L)

J N+2'

(2.1)

The relation

Z 2N-1' Z 2N-2' '"' Z N

n+1

1, 1

J 2 (n+1) \ 1, -1

I X .

1, -1

(n + 1)

. X

1, 1

1, "I

_1
sT 2

1

1. 1

U/^ \l, -1
V

1, 1\ /I, 1

x...*[

n

X

1, "I

.1, -1,

_>

1, 1>

^2 ^ X \l, -1,

, /U , U
1 / n n

^2

U , -U
n n

(2.2)

holds clearly.

As the theorem holds for n from the assumption,

-7-

x n = u

n

\

N-l

y. =A (z ,z 1 ,...,z N _ 1 )u.

1

'N

r '^o ,J l' ••*"N-1 / '*I

>

(2.3)

hold, where < i < (N - l).

In Eq. (2.1), letting

z . _ = z

for < i < (N - 1),

X n =

'1*

z l> z 0'

> Z N-1

Z N-1' Z N-2'

., K

holds. Therefore applying the theorem to X, ,

X = U

1 n

y

N+l

U

>v

y 2N-l'

y (2A)

y n©i =</n ^i' z I"-- Z N-l )u i =VN ( VVl-' Z lH )u i

1 Z n©i ~ ^ (y r y N+l^°^ y 2N-l )u i

^

hold.

Now, let

-8-

A, =

>

X (N-1)

>

(2.5)

'N

^N+l

A.

x

2N-1 7 J

such that

^

I < A 1 + V =

N-l

>

N

N+l

| (A,-A 2 )

(2.6)

y 2N-l'

Then from Eqs. (2.1) through (2.6), the relation

-9-

Un+1 \o a) Un+i

, u u

/ n n

U -U

n n

A i °

*2

u , u

n n

U , -U
n n

A l +A 2

u — u , u

A, ■ Ag

U

n 2 n n 2 n

\~*2

A l +A 2

u , u — u

n 2 n n 2 n

X Q , X-j^

x x , x Q

= z

(n+1)

holds. Therefore,

A l °
(n+l) n+1 \ Q / n+1 n+

x

Vi < 2 - 7 »

x

(2N-1),

holds .

From Eqs. (2.5) and (2.6),

X i = y i + y N+l

X N+1 == y i ~ y N+l

hold, where < i < (N - 1). Therefore, from Eqs. (2.3) and (2.4),

= n/n (V z l— Vl^i WN ( V Z N+l--- Z 2N-l )u i

N ^ V z i>--> z N-r V z n+i' • • • ' z 2n-i ■

u.

(2.8)

■10-

*N+i =/N ( W--- Z N-1 )U 1 -^ ( V Z N + l'-"' Z 2N-l )u i

(u.
1
-u.

(2.9)

can be obtained, where < i < (N - l). Letting U . = (v , v,, . . . , V 2N _]_)^

N+l

v. =

l

- r 1

^2 \ u.

>

1 f U i

N+l

J"s

•u.

(2.10)

holds, since

i / U » U

u i ="F n n

n+1 ^2 V U , -U

x n n

/here < i < (N - l). Therefore, from Eqs. (2.8), (2.9), and (2.10),

x

x. =n/2N (z ,z 1 ,...,z 2N _ 1 )y.

"\

}

z ] v

2N-1 ; N+i

(2.11)

can be obtained where < i < (N - l).
From Eq. (2.11), the relation

(W-'W =nS> ( W"-' z 2n-i )( V v i"-" v 2n-i )

= ^ (VV-' Z 2N-l )U n + l

holds. Therefore the relation

■ 11-

( V Z 1--- Z 2N-1 ) = ^ ( V X r-'Vl )U r 1+ l

v2N

holds since U n U , = E , • where E . is the unit matrix of order n+1.
n+1 n+1 n+1 n+1

From Eq. (2.12),

Z i ^ ( V X l^*^ X 2N-l )v i

can be obtained, where < i < (2N - l).

The above description has made it clear that the theorem holds for
(n + 1).

Theorem 2.2. In Theorem 2.1,

T„ T

u.Z = x.u.

in li

n T

holds, where < i < (2 - l), and u. means the transposed matrix of u.

Proof . From Theorem 2.1,

x x u x l

u T Z = u T U . |U = (0,... ,0,1,0,. ..,0) I . JU

in\ . In I , /n

/ \ ° '

X N-l/ \ X N-1>

= (0, . . .,0,x.,0, . . . ,0)U = (x.u. _, x.u. ,,..., x.u. , v )
' ' ' i' ' 7 ' n l lO i ll l i(N-l)

T

x. (u.-.,u. ,, . , .,U. /„ ,\) = x.u.
i lO ll i(N-l) l l

can be obtained, since

■12-

T

U n = (u ,u r ..., Vl ) =

l N-l

3. GENERAL THEORY OF MOST EFFICIENT CODES

Definition 3-^- » 1 code

Let i be a positive integer, ^ i < (2 - l), and let the binary
expression of i be as follows:

i = x. / x2 + ... + x.,2 + x._.

i(n-l) ll iO

The

n, let the binary code (x. , 1 u...,x.,iX Jft ) be called "i" c

i(n-l; ll iO

ode

Notation 3-1 . dist(i,j)

Let the Hamming distance between i code and j code be expressed by
dist(i, j).

From Definition 2.1, Definition 3«1 and Notation 3«1.>

dist(i, j) = i e j

(3.1)

clearly holds

Definition 3.2. Matrix H(n, p)

The matrix H(n, p) is a square matrix of order 2 and is defined as

follows :

00'

h 0l' h 02'

> h

0(N-1)

H(n,p)

h 10' h ir h 12' ■•■' h l(N-l)

h 20 , h 21 , h 22 , ..., h 2(N _ l}

h (N-l)0' h (N-l)l' h (N-l)2, *' h (N-l)(N-l) /

(3.2)

-13-

-1k-

where N = 2 , n > p > 1. Here,

h . = 1 when dist(i,j) < p

h. . = when dist(i.j) > p
ij -

>

From Notation 3»1>

dist(i,j) = i©j=Oe(iej) = dist(0, i e j)

holds. Therefore,

(3.3)

h . . = hu. / . . \

(3A)

can be obtained.

Now, define h. as follows
7 l

h. = h n .
l Oi

(3-5)

Then,

h n = h. .
li

lu = h.

i,i«

= h

h.

(3.6)

^-1 " h i,ie(N-l) h ie(N-l),i

can be obtained for any i (0 < i < N - l). Therefore, the matrix H(n,p)
defined by Definition 3.2 can be expressed by

■15-

H(N,p) =

h Q , h L , h 2 ,

h> V h y

...,h

le(N-l)

V h iel' h ie2' ••" h ^

ie(N-l)

(3-7)

.V-l' \-2' ^-3' '■'>

.., K

where

h = h. . = 1
li

(3-8)

From Definition 3.2 and Eq. (3»6)>

h o + h i + •'• + \-i = h io + h u + ••• + h i

(N-l)

= K(n,p) (3-9)

can be obtained, where

K(n,p) = C„ + C-. + ... + C

v ,r n n 1 n p-1

(3.10)

Example 3 » 1

H(n,l) =

= E.

K(n,l) = n C = 1

Clearly, H(n, l) is a unit matrix of order N.

Example 3*2

Example 3 • 3

H(n,n) =

■16-

K(n,n) = CL + O. + CL + . . . + C _ = 2 n - 1
n n 1 n 2 n n-1

H(3,2) =

K(3,2) = 3 C Q + C^ = 1 + 3 = k

Theorem 3-1 - The matrix H(n, p) can be transformed to a diagonal matrix by the

orthogonal matrix U , that is,

n' '

H(n,p) = UAU
' n n

and

\ =Vn (VV-ViK

hold, where

-17-

h i = ^ ( VV-Vi )u i

A =

\ °

N-l

Proof . Applying Theorem 2.1 to H(n, p), the theorem clearly holds.

Now, the most efficient coding condition is equivalent to the following
condition: that is, to find a maximum m such that

H = E
m

(3.11)

where

H o =

ih~, h. . , h. ...... h.

12 13 1 m

h i 2 ®V V

h. .,..., h. .

2 3 2 m

h. . , h. . , h^, . . . , h.

3 13 2 3 m

(3-12)

h . . , h . . , h . ...... h_

ml m 2 m 3

and E is the unit matrix of order m.
m

Therefore, from Theorem 3-l> "the most efficient coding condition is

also equivalent to the following condition: that is, there exist u. , u. ,

X l X 2

u. for maximum m such that

1
m

-18-

H =

U

T

u.

A(u. ,u. , . . . ,u. ) = E
1, 1 ' 1 m

12 m

(3-13)

in)

where

u

U n = (u 0)Ul ,...,u H ) =

\u

N-li

that is, u., etc., means the transposed matrix of u., etc,
Now, let

V =

(3.14)

m/

T
VAV = E for maximum m.

m

(3.15)

Asu. , u. , ..., u. are column vectors belonging to the orthogonal matrix U ,
1 1 1 2 1 m

T

W = E

m

(3.16)

-19-

can be obtained. Therefore, from Eqs. (3«i5) and (3.16),

T T

VAV = VV =

tn

.*. V(A - E N )V T =

(3.17)

can be obtained, where E is a unit matrix of order N and the right-hand side
"0" of (3»17) means the zero matrix of order m (where every element is zero).

Definition 3-3 » Define the vectors £„, C,, , ..., i , as follows

V

T
u.

' r„ ^o ;5 l"" ,& N-l^

>/n

ml

There exist m independent vectors among i , £ , ..., L since V
consists of m row vectors belonging to the orthogonal matrix U .

Therefore, as understood clearly from Eq. (3. 17) and Definition 3°3>
the most efficient coding condition may be found by finding the solution of the
following equation:

(£ ,5 1 ,...,.£ b . 1 )(a - V«o' c i'-"'Vi ) = ° (3 - l8)

such that the number of the independent vectors among ( £ n , £, , . . . , C ) becomes as
large as possible.

-20-

Now, some relations which hold among i , £ , . .., C are described

below.

Definition ?>.k . Operation s

Given two matrices A and B whose number of rows and columns are n
and m respectively, i.e.

' a ll' a l2' "*' a im'

a 21 , a 22 , . .., a 2m

A =

and B =

b lx , b 12 , ..., b lm
b 21 , b 22 , ..., b 2m

a,, a , . . . , a

nl n2

nm/

b .., b _, ...fti

nl n2 nm

Define A a B as follows

' a ll b ll> a 12 b 12' "■'' a T- b
^l^l' a 22 b 22' '"'' a ° mlD

A b B

a , b , , a _b _, . . . , a b

nl nl' n2 n2 nm nm,

Definition 3.5. |.

Define | . as follows
1

Vn

U =

(l ,^

•'^N-l^

that is, l , |,, . .., I N are the column vectors of vN U . Accordingly,

I . = VN u .

(3.19)

holds .

-21-

Theorem 3-2

6 t«i = e t ■ h

holds, for any t, i (0 < t, I < N - l)

Proof. When n = 2,

n u, -1,

x

1, 1
1, -1

1, 1, 1, 1

1, -1, 1, -1

1, 1, -1, -1

1, -l, -1, 1

0' 1' P' v

holds. Therefore

f 3-

can he obtained. Therefore, the theorem holds for n = 2.

Assume that the theorem holds for n. Then, by mathematical induction,
the theorem also holds in the case (n + l).

7 2 (n + l) y m J^ [ ^

2 n U, ^2 n U
n n

n+1

1, -1

sf^U , -^

(3.20)

u

n,

holds, clearly.

Since the theorem holds for v2 U by the assumption, the theorem
clearly holds for

r

-22-

Therefore, letting \l2^ n+1 '

U , be expressed by

^^ ' U n + 1 = (VV-VrV-W^ (3.21)

the theorem holds for

2%

n ) = 'VV-'Vi 1

n.

(3-22)

Since

and

^u n = (i^,...,!^)

J^

V2 n U. , N/2 n U

U

n+1 \ . O?

^2 n U , W2 n U
* n r

(3.23)

i-l

holds. Therefore,

■:']-

W

-5

1
-1
■1

= \»

m \ m1 *i

, -1

holds where < I < N - 1.

The above discussion has shown that the theorem holds for (n + l)

Theorem 3-3

^ = c t H H

holds, for any t, I (0 < t, Z < N - l).

Proof. The result is clear from Theorem 3.2 and Definition 3-3<

Definition 3«6- z.

Define z n , z, , z , . .., z , as follows:

•4 z, = (1,1,...,1)L,

that is, z. is ~r- multiplied by the sum of all elements of the vectors £
1 n/n

Theorem 3»^

C t ' ; I ■ /H z tel

for any t, I (0 < t, i < N - l) .

■2k-

Proof .

#i

= (1,1,. ...,!)(£ a (,«) = (1,1,...,1)L S (from Theorem 3.1)

'£

f£

- z

te£

(from Definition 3.5)

From Definition 3-3 and Theorem 3«^>

T 1

V V = -

N

.T
5 N-1

(^ ^ 1 ,...^ N _ 1 ) -

N

C T C C T C C T C C T C
b CTO' b b l' b S 2' '"' b O b N-l

C T C C T C C T C C T C

\ C T c C T c C T c C T c

\ b N-lV b N-l b l' b N-l' b 2' *' b N-l b N-l (

_1

nTn

rz , z x , z 2 ,

-i /T\T * -1

' Z N-1

J l' V Z 3' "•' Z 1©(N-1)

(3-21+)

lZ N-l' Z N-2' Z W-3' "*' Z

can he obtained .

Now, following the preliminary discussion above, the most efficient
coding condition is discussed below.

Definition 3«6. Define A' ,\! as follows

-25-

/V 1

A' = A - E N =

V 1

\ /*

•(N-l)

4

/

- 1 ' \ S-i/

(cf. Theorem 3.1)

Definition 3.7. Z

Define Z as follows

= n/n V V =

'1' 2'

z l> V

V Z V

'V

' Z N-1

Z N-1' Z N-2' Z N-3' °°°' Z

From Eq„ (3«17) and Definition 3-6,

VA'V T =

(3o25)

can be obtained. Therefore

(V T V)A'(V T V) =

(3.26)

can be obtained. Conversely, from (3.26) and (3.16)

V(V T V)A*(V T V)V T =

VA'V T =

can be obtained. Therefore, when W = E holds, the condition (3«25) is

m

equivalent to the condition (3.26)

-26-

From Eq. (3-26) and Definition 3.6,

ZA'Z =

(3-27)

can be obtained. Therefore, to find the most efficient coding condition, find
the maximum m such that

W 1 = E

>

ZA'Z =

(3.28)

T T

Theorem 3.5 . When VV = E and V V = Z, the rank of Z is m and the characteristic

values of Z consist of "l" (m times) and "0" (N - m times).

Proof. Since W = E holds,

m '

det(\E - VV T ) = (X - l) m
m

can clearly be obtained.

On the other hand, since

holds generally,

T T N-m

det(\E„ - V V) = {det(\E - W )}X
N m

det(\E N - V T V) = (\ - l)^ (N - m)

(3.29)

can be obtained.

T,

Applying Theorem 2.1 to V V,

/ °'

Z = n/n V V =

z . , z.

-27-

z l' ••" Z N-1

., ^ iel , ..., - ie(N _ 1 )

Z N-1' Z N-2' •**' Z

= U

U

x

(N-l)

(3-30)

can be obtained.

From Eqs. (3.29) and (3«30)> "the rank of Z is m and the characteristic
values of Z, i.e., x„, x, , ..., x w _ 1 consist of "l" (m times) and "0" (N - m
times) .

k N-l

From Theorem 3-5> finding the condition for the most efficient codes
can also be reduced to finding the solution of equations

T

W = E

m

ZA'Z = J

(3.31)

with the maximum rank of Z.

Remark 3.1. From (3. 30),

-A (w- z N-i )u i

can be obtained. If x. = x. = ... = x. =1 and the other x. = 0, i_, code,

L, 1_ 1 1 1

12 m

i,. code, ..., i code are all of the most efficient codes.
2 m

h. CALCULATION AND SOME PROPERTIES OF EACH \.

The value of each X. is given by the formula of Theorem 3-l> i.e.,

X. =nT N (h ,h 1 ,...,h N _ 1 )u.

where each h. is decided uniquely by the value of n and p.

Another method of calculating each X. and some properties of X. are
discussed below.

Theorem 4.1. p = 1 if and only if \„ = A., = ... = X„ , = 1,
^ J 1 N-l

Proof . If X = X =

N

, = 1, from Theorem 3«1*

h i = ^ ( VV--ViK "z (1 ' 1 '-" 1)u i =

Vn

1 when i =
when i /

can be obtained. Therefore,

H(n,p) =

can be obtained. Therefore, p = 1.
Conversely, if p = 1,

h~ = 1, h. = for i /
l '

can be obtained. Therefore,

/.

. = "/n (1,0,0, . ..,0)u. = 1 for any i (0 < i < N - l)

Therefore, the theorem holds.

-28-

-29-

Theorem 4.2

\ Q + ^ + . . . + X N _ X = N

^2 .2

x + \ x +

+ \ N _ ] _ = NK(n,p)

Proof. From Theorem 3.1*

+ \ 1+ ... + X N-1 =Vu (h ,h r ...,h N _ 1 )(u + u 1+ ... + Vl )

= ^N (VV— 'W

nTn

= Nh = N

can be obtained. From Theorem 3-l>

H(n,p) = U AU
' n n

2 2

H = U AU
n n

X\ =^N (^^...^^^u.

can be obtained, where

ho \

H(n,p) s (^J^,...,^) =

T

T
S-l

Therefore,

■30-

,2 .2
X + \ +

+ Sli =n/n ^oVfe-fei^o + u i + ••• + Vi }

= ^n (rg£ £^,.

T

Vn-i^

n/n

= N£ J!, = N(h Q + 1^ + ... + hjj^) = NK(n,p)

Theorem ^-.3 . The following relations hold:

(1) \ Q = K(n,p)

(2) Any \ for 1 < i < N - 1 are

\ = K(n,p) > X = integer

where the equality holds if and only if p = 1

Proof. From Theorem 3«1;

\ ± = VN (hQ,^, ...,h N _ 1 )u i = (h^h^ .. •^ h N _ 1 )i i = integer

can be obtained,

Since each h. is equal to 1 or 0,

(h ,h 1 ,.„.,h N _ 1 )u > (h ,h 1 ,...,h N _ 1 )u.

and

\ = A (h ,h 1 ,...,h N _ 1 )u = h Q + 1^ + ... + hjj^ = K(n,p)

-31-

.*. K Q m K (n,p) > \.

can be obtained.

Suppose that there exists i, 1 <. i < (N - l), such that

Then,

x . v

can be obtained,
Since

(V h l'---' h N-l )u O = 'Vl'-'Vl'"!

(h ,h 1 ,...,h N _ 1 )(l - 5 .) =0

n

d - e ± ) -

\ i

i

+ 1
+ 1

+ 1

each element of (I - |.) is equal to 2 or 0, i.e., non-negative, and there
exist elements except the first row element such that the value is equal to 2,
(Clearly, there is no case except p = 1 for n = 1.) Therefore,

(h ,h 1 ,...,h N _ 1 )(i - |.) =

holds if and only if h =1, h, = h =
p = 1.

V:

0. This is the case where

-32-

Theorem k.k

where

where

X = X = ... = X

12 n

X = X =.....= X

r +r r i +r o r i +r

12 13 n-1 n

X = \ = ... = X

r, +r +r_ r, +r_+r, r ^+r , +r

12 3 12 4 n-2 n-1 n

X = X = ... = X

r, +r +...+r . r,+r_+...+r +r r^+r.+.^+r

1 2 n-1 1 2 n-2 n 2 3 n

Q n-1 n-2 o

r 1 = 2 , r 2 = 2 , . . . , r n = 2 = 1 ,

Proof. Consider any permutation of the correspondence

X i(n-1)' X i(n-2)' ■•" x il' X i0

>-. ^ X , jf . . ■ <, X . ^ x .

1S (n-l) 1S (n-2) 1S 1 1S

1 = x. / ,\2 + x. / „x2 + . . . + x.,2 + x. n

i(n-l) i(n-2J il i0

that is, any change of the column position of codes.

From the definition of H(n,p), i.e., Definition 3-2, H(n,p) is

invariant under this change.

In H(n,p) = U AU , U is also invariant under this change.
' n n' n

Suppose that A becomes V under this change. Then,

H(n,p) = U AU = U ^U
7 n n n n

holds. Therefore,

-33-

A = V

can be obtained. Therefore, A has to be also invariant under this change
As mentioned above,

\ = X = . . . = \

12 n

\ = \ = ... = \

r,+r_ r-,+r_ r , +r

12 13 n-1 n

\ = X = ... = \

r,+r^+ ..+r . r,+...+r +r r.+r,+...+r

1 2 n-1 1 n-2 n 2 3 n

must hold.

Definition k.l . Extension of the definition of H(n, p) (cf., Definition 3-2)

Define H(n,p) of the. matrix of order 2 where n < p and p = as
follows 1

a, 1, ~., 1'
1, 1, ..., 1

H(n, p) = I when n < p,

1, 1, ..., 1

'0, 0, . ..,

0, .0, ...,

H(n,0) = when p = 0,

.0, 0, ..., 0/

_ 3 4-

Theorem 4.5

H(n,p) =

H(n-l,p), H(n-l,p-l)
H(n-l,p-l), H(n-l,p)

holds where n > 0, p > 0.

Proof . It is clear from Definition 3-2 and Definition 4.1.

Definition 4.2 . Extension of the definition K(n,p) (cf., (3-9))
In general, define K(n,p) as follows:

K(n ' p) = n C + n C l + '•• + n C p-l
K(n,p) = 2 n

K(n,o) =

when n > p > 1,
when < n < p,
when n > o, p = o,

From Definition 4.2,

K(n,n) =2 - 1

K(o,p) =2=1 for p > o

>

J

(*.l)

can be obtained,

Remark 4.1 . It is clear that the theorems, etc., presented until now also hold
if the definitions of H(n,p) and K(n,p) are extended like Definitions 4.1 and 4.2,

Theorem 4.6

\ Q = K(n,p)

X + X = 2K(n-l,p)
1

IV

\_ + _C,\ + \ = 2 K(n-2,p)

2 1 r, r -] +r p

3 1 r x 3 2 ri +r 2 r ! +r 2 +r 3

= 2 3 K(n-3,p)

\~ + C,\ + C n \ +...+ C n \ + \ =2 K(n-s.p)

sir, s 2 r,+r_ s s-1 r, +r^+...+r , r.+r^+...+r '*'

1 12 12 s-1 12 s

\„ + C\ + CLA. +...+ C n \ + \

■1 n2r i +r 2 n n_1 r l +r 2 + "- +r n-l

n"n-l"r-, +r^+. . .+r *r n +r +. . . +r = 2TC(o, p) = 2

holds.

Proof,

,U - , U . \ /A, \ / U 1 , U

tt/ \ TT /\ TT 1 / n-1' n-1 \ / 1 \ n-1' n-1
H(n,p) = UAU = -

1 n-1 n-1 / \ ;2 ' \ n-1 n-1

A l " A 2
— - U ,, U n -~; — - U

A, h Ag

n-1 2 n-1' n-1 2 n-1

A 1 - A 2 A 1 ■ + A 2
^ U n-1 ~ 2 U n-1' U n-1 — 2 U n-1 /

holds, where

A =

A l °

*B

On the other hand, since

H(n,p) =

'H(n-l,p), H(n-l,p-i;

^H(n-l,p-l), H(n-l,p)

holds from Theorem k.5,

-36-

A- + iL
H<n-l,p) = u n _ x — ^ U n-1 (4.2)

can be obtained. Therefore, from Theorem 4.3 and Eq. (4.2),

\ n + K
r

= K(n-l,p)

\ Q + \ r = 2K(n-l,p)

must hold, where r, = 2

Similarly, since

'H(n-2,p) H^^p-l)'
H(n-l,p) =

H(n-2,p-l), H(n-2,p)

holds from Theorem 4.5,

k n + X + \ + \ = 2 2 K(n-2,p)

^ r 2 r x +r 2

\„ + _C,\ + \ = 2 2 K(n-2,p) (4.4)

2 1 r r +r v '*' y '

must hold since

\ = \

r l r 2

n-2
holds from Theorem 4.4, where r = 2

Similarly, in general,

\_ + C..\ + CL\ +...+ C n \ + A. = 2 S K(n-s,p)

sir, s 2 r, +r^, s s-1 r,+r^+...+r . r, +r^+...+r

1 12 12 s-1 12 s

can be obtained, where r. = 2 for 1 < i < n and 1 < s < n.

Accordingly, this theorem holds.

5. SOME PROPERTIES OF C

An independent vector in £ , £ , . .., £ , is not determined uniquely,
Therefore, independence is defined as follows.

Definition 5.1 . Independence of the vector £.

Let £. be called an independent vector of £_, £,, . .., £ -, when it
satisfies the following condition: £. cannot be expressed as a linear combina-
tion of £_, (L , .... £. -, , i.e., there do not exist a_, a,, ..., a. , such that
1 l-l 1 l-l

6 i = a 0^0 + a i C l + '•• + a i-l £ i-l'

where a~, a,, ..., a. , are real numbers.
1 l-l

Definition 5.2 . Dependence of the vector of £.

Let £. be called a dependent vector in £ , £ , ..., C , , when it
satisfies the following condition: £. can be expressed as a linear combination

of £_, £,, . ... £. -, , i.e., there exist a~, a,, ..., a.
1 l-l 1 l-

1

such that

5 i = a o^o + a A + ••' + a i-A-l'

where a_, a,, ..., a. , are real numbers
1 l-l

Definition 5.3 . Generator of £_ , C, ..., C ,

Let £ Q , t^, £ 2 , C p, o.,, C 2. lDe called generators of £ Q , £ ,

b N-l

Theorem 5.1 . When £. (0 < i < 2 S - l) is a dependent vector of C, L, «.., £ . .

each of £ (n - 1 > t > s) is a dependent vector of C, , C, ..., L

_. . U J- IN — -L

2 +1

■37-

-38-
Proof . Since £ . is a dependent vector, £. can be expressed by

S i = a C + a l^l + ••• + a l-l C i-l

where < i < (2 S - l).

Therefore,

h B e 2 t = (a o^o + a A + ••• + a i-A-i> E ^ t

2*+l ° 2 t 1 2 t + l "- 1 2^(1-1)

where 2 n_1 > 2 1 > 2 S

Therefore, from Definition ^.2, £ is a dependent vector of £ ,

2 +i

^1' •" , Vl'

Theorem ^.2 . When a generator C, is a dependent vector of C, £ . .., t , every

£ (0 < i < 2^ S+ ' - 1) is a dependent vector of C, C, . .., £ , .

2 S +i U X W_1

Proof. Since £ is a dependent vector of £_, C, .... C T , , £ can be
pS ^ 0' l 7 N-l s

expressed by

C, = a n £ + a, £,+...+ a £

2 S ° ° ! 1 (2 S -1) (2 S -1)

Therefore,

£ » C. = (a n C + a.. L + ... + a £ ) s C.

2 S X ° ° X X (2 S -1) (2 S -1)

£ = a £. + a. L ,+...+ a £
2 S ei ° X 1 iel (2 S -1) ie(2 S -l)

can be obtained. Since < i © j < (2 S - l) for < j < (2 S - l) holds, £

2 S +i
is a dependent vector of £ , £ , ..., £

J9-

Theorem 5.3 . When £ is a dependent vector ol' i, £ ..., £ N _-,> ^pi+1 is also
a dependent vector.

Proof. Since C_. is a dependent vector of £_, C , . ... L T ,,
2i 1 N-l

C 2i = Vo + & A + "' + a 2i-i rJ 2i-l

.'. 5 2± ■ 5 X - (a^ + a^ + ... + ag.^^.^) * ^

can be obtained. Here since

< j © 1 < 2i - 1 for < j < (2i - 1),

can be obtained. Therefore, C . . is also a dependent vector of £., L, ....

2i+l 1

Vr

In general, the following theorem holds as an extension of Theorem \$.1
and Theorem 5-2.

Theorem 5.h. When £ is a dependent vector of C_. C, . ... L, , ,
s, s Sfl 0' l 7 N-l

2 +2 +. . .+2

S ^
b is also a dependent vector, for any i, < i < 2 -1 and

S l S 2 S i

2 +2 +...+2 +i

s > S l > S 2 > ' ' * > S £ - lo

Proof . Since £ is a dependent vector of £„. C, . .., C ,

s, s s « U J- IN - _L

2 X +2 2 +2 ^

£ „ „ = a n^ + a C + o . . + a £

S S B/j 1 1 s s s, s s s,

2 +2 %...+2 * 2 +2 +...+2 -1 2 +2 N-...+2 -1

s s s/ 1 1 1 s s s p s s 2, 1

2 -^2 d +...+2 * 2 +2 -rf-...+2 -1 2 +2 +...+2 -1

can be obtained. Since

-40-

s l S P S R
< j © i < 2 + 2 + ... + 2 -1

holds f or < j < 2 + 2 ■ + . . . + 2 - 1 and for < i < 2 - 1,

£ = a J, . + ...+ a £

s, s S/, u i s n s i s /> s r> i s ^

2 +2 2 +...+2 +i 2 °+2 +...+2 -1 (2 °+2 +2 -l)©i

can be obtained, where the right-hand side is the linear combination of £_, £, ,

S S l S ^
2 +2 +...+2 -1

Therefore, £ is a dependent vector of C n , C-, , • • • , L T -, ■

s, s . S| u 1 1M-1

2 +2 +...+2 +i

Theorem \$.5 . When £ is an independent vector of £>„, C, . .., £ , , £. is also
an independent vector for any i, 1 < i < (2 - l).

Proof . Suppose that there exists a dependent vector £. of £ , £ , . .., £ , .
Then

h = a o^o + a A + ••' + VA-1

can be obtained, where 1 < i < 2 - 1,

Now,

l /..s , \ . 11 l-l l-l /r ,s . \ .

accordingly,

C = a £ + a, £ + ... •+ a , S _ (5-1)

(2 S -1) U (2 S -l)ei X l©(2 S -l)©i (i-l)e(2 S -l)ei

holds. Since

< j © (2 S - 1) © i < 2 - 1

-Id

holds for any j (0 < J <- 2 S - L) and for any i (1 < i < 2 S - l) and for

j < (i - l), the right-hand side of Eq. (5-1) is a linear combination of some

of t>~, £,;...;£ • Therefore, i becomes a dependent vector of C A , L,

X (2 S -1) (2 S -1)

•••> Vl'

This contradicts the assumption of the theorem. Therefore, £. is also

an independent vector of i , £ , ..., i .

In general, the following theorem holds as an extension of Theorem 5- 5*

Theorem 5.6 . When £ is an independent vector of ^ n , C, ...,

S, S Sp (J 1

2 +2 +...+2 -1

C , , £ is also an independent vector for any i, where

s-, > s > ... > S| > 1 and 1 < i < (2 - l) .

Proof . Suppose that there exists the dependent vector £
of £ Q , i ± , ..., i^_ ± where 1 < i < 2 - 1. Then

£ = a C + a i + ...

s a s,n s 11

2 +2 +...+2 U lj +i

+ V 1 + 2 S2 + ... + 2^- 1 ) + i2V 2 + ... + 2^- 1 l(i-l)

accordingly,

^ s s s ) E ^ 2 = ( a ^o + ••*
2 X +2 2 +...+2 ^ -l) +i (2 ^-l)©i

+ a £ ) & t,

2 Sl +...+2 S( ' e " l) + i 2 Sl +... + 2 S(i " l) + (i-l) (2 i -l)©i

can be obtained. Therefore,

-42-

£ = a_£ + a. £ + .

s s b- s f 1 So

(5.2)

+ a C,

2 X +2 2 +...+2 ( ^ _l) +i {2 1 +...+2 S( ' e " l) + (i-l}©(2 S ' g -i;

ei

can be obtained. Since

holds for any j < (i - 1), where

0<j<2-l

and

l<i<2-l

Therefore, the right-hand side of Eq. (5*2) is a linear combination of some of

i~, £,,...,£ . Therefore, £ becomes a

1 s s s, s s s.

2 +2 +...+2 -2 2 +2 +...+2 -1

dependent vector of £ , £ , . .., C N _-,_-

This contradicts the assumption of this theorem. Therefore,

£ is also an independent vector of £ , £ , ..., £ , .

S-. s s« u 1 1M-J-

2 +2 +...+2 -1

Theorem 5.7. When £ , „ is a dependent vector of £_, C, ...,

— L ^n-1 ^n-2 ^n-s 1

2 +2 + . . . +2

C T , , it can be expressed as a linear combination of £„, £ , £ , ,
N-l 0' p n-s n-s+1'

£ , . . ., C » that is,

3'2 n - S (2 S -2)2 n - S

£ n = a ^^ + a, C + ... + a £

2 n - 1 + 2 n - 2 + ... + 2 n - S °° X 2 n " S (2 S -2) (2 S -2)2 n - S

2 n " S 2 n_S+1

3'2

n-s

a"" 1 + 2 n " 2 + ... +2 n - s = (2 s - )

.n-1

,(n-s)

(2 S - 2)2

n-s

where 1 < s < n. Accordingly

C t o = a~£. + a,£ + a^£ +...+ a £

_n-l _n-2 ^n-s . i 1 „n-s . 2 ^ ~n-s . /„s \ /r ,s v^n-s .
2 +2 +...+2 +i 2 +i 2-2 +i (2 -2) (2 -2)2 +1

(5.3)

n-s

can be obtained for any i (0 < i < (2 - l)).

Pro of. From Theorem 5.2, £ , _ is a dependent vector of £_, C,

~n-l o n- 2 o n_ s . Cr 1'

2 +2 + . . . +2 +i

..., £ N _ X for any i (0 < i < (2

n-s

l)). Therefore, there exist at least 2

n-s

dependent vectors in £ , £ , ..„, C

Now the generators in £^, £ > £ ■, » C > . . . * £ >

2 n-s' S £ n-s + l' 3 . 2 n-s' V-s)2 n " S

Since

^O'^n-1' "'>*> n-s^

1

1

-1

1 -1
1 1

1
-1

(n-s)

1 -1

-kk-

the vectors C>~, i , £

n-s
2 2

quantum vectors

, . . . , £ are constructed by the 2

(2 S -2)2~

n-s

ll\

and

-i/

n

Therefore, there exist at most = 2 independent vectors in £_, £ ,

' p n-s 7 P n_s

C n, .... £ . Here, if and only if the number of elements of each

n-B+1' ( 2 s -l)2 n - S
^ is 2 , the number of the independent vectors is 2 .

n-s

From the description above, there exist at least 2 dependent vectors

n ( n— s )
Therefore, the number of elements of each £ is equal to or less than 2 - 2

Therefore, the number of independent vectors in £ , C , £

5

,n-s

0' J „n-s' J ^n-s+l' "*'

is at most

(2 S -1)2'

,n-s

= 2'

1.

On the other hand, the number of vectors of £_, £ , C -, »

Cr p n_s p n-s+ - 1 -

£ is 2 . Therefore, £

(2 S -l)2 n - S

(2 S -l)2 n - S : ^2 n " 1 + 2 n - 2 + ... + 2 n - 2

can be expressed

as a linear combination of £_, C , C n *

p n-s' n-s+1'

Since

(2-2)2

n-s

2 n -\ 2 n - 2 ,

, a"" 3 > i

N n-s

holds for any i (0 < i < (2 -. l)), the subscript of each £ of the right-hand
side of Eq. (5.3) is between and (2 n ~ 2 + 2 n ~ 2 + ... + 2 n_S - l). Therefore,

Eq. (5.3) holds.

Theorem \$.8

r r 3 • r
k k+1 3 k

N-r -2r. N-r
s k s

N-l

-• •-

N-r -r.
s k

-45-

When every £. for N-r - r u .5 i 5^" 1 - L '-> a dependent vector of

(, , i , ..., £ , £„ can be expressed as a linear combination of (, , £ ,

s k k

t , S3. , ..., £ N _ r _ 2 "here ^ > r > r R and ^ = 2 ' , r g = 2 E ,

(k+1) k s k

o n ~ S

..., r s = 2 ,

. , r = 2 , that is

Vr -r. = a 0^0 + a l^r v + & 2^2-r v + '•• + a N-r a -2r,/r Vr -2r^
sk k k s k K s k

Accordingly,

5 (N-r -r n )+i ~ a 0^i + a l^r+i + °" + Vr -2r, /r Vr -2r +i

x sk k skksk

can be obtained for any i (0 < i < (r - l))

Proof o As in the proof of Theorem 5»7^ £ n j £ > ^ , ,, .., ^

r k k *' ^s "k
are constructed by the quantum vectors

N-r -2r, ? N-r -r,

s ^k

and

each with r, elements. Therefore, the number of independent vectors in £_, £ .>

2 n r k

C„ , ..., C T is at most — . Further, if and only if the number of elements

k k k ^n

of each t, is 2 , the number of independent vectors in £_, £ » ...» (L, is — .

0' r. N-r. r.
k k k

From the assumption of this theorem, the number of dependent vectors of

£-., £-, , ..., C„ -, is at least r + r. . Therefore, the number of elements of each
1 ' N-l s k

£ is not more than N-r - r, . Therefore, the number of independent vectors in

N-r-r /N-r \

£~, i , (L , . . ., C T is not more than = - 1 1 .

r. 2-r/ N-r, r. \ r. /

k k k k < \ k /

-k6-

On the other hand, the number of £_, £ , £_ , .... £„ is

r. 2r. N-r -r,
N - r k k s k

5

Therefore, C, can be expressed as a linear combination of

r n ' N-r -r,

k s k

b 0' V ' b 2r, ' "' b N-r -2r
k k s k

Since

r l' V '"" V ■"' r k > 1 £ °

holds for any i (0 < i < (r -i))> the subscript of each £ of the right-hand

i£— J-

side of Eq. (5.^) is between and (n-r - r - l). Therefore, Eq. (5°^) holds,

S K.

Theorem 5°9 « Let n p,^ n n > n -> ■••* n / \ be as follows:

u 1 2 / (n-k;_^s

n n : the number of independent vectors of £_, C, . „., ^ TJ _-,

in C , C £,...,£

° 1 ^ (2-1)

n, : the number of independent vectors of £_, C, ..,, ^• M _-,
2 k 2+1 2+2 2 U+lj -l

n

: the number of independent vectors of £ , £ , . .., £ ,

in ^(* + D< S 2 u + D +1 ' 5 2 (k + D +2 ' •••' ^.^

l / , \ : the number of independent vectors of £_, £, , ..., L T n
/ 2 (n-k)_ 1 x 1 N-l

N-2* N-2 +1 W

Then

n_ > n n > n > . . . > n / ,\ >

- 1 - 2 - - ( 2 ^ ^-1) ~

holds, where < k < n - 1,

Proof. It is clear.

-U7- •

Theorem '■> . LP . Rearrange the generators £ , £., £ , ^ ,., . .., £ n _ L of £ C,

..., £„ in the order. (, , £ , L £ p , ..., £ p . Then the order of vectors

after £ becomes: . ... £ ~» £ n <>> ^ ^ > £ i ^ > ^ ^ >

n-P n-2 n-1 n-2 n-2 n-1 n-2 n-2

2 2 2 +2 2 +1 2 +2 +1 2 +2

^ n-1 n-2 ' ''■' n-2 ' n ' ^ n-1 ' ^ n '
2 n +2 +2 2 -2 2-2 2 -1 2-1

Proof . The vectors after C, in £ , Q , . . . , C have always the factor

2 " in their subscripts and have any combination from 2 ,2 , ..., 2, 1

in their subscripts. Therefore, applying the substitution:

0, 1, 2, 2 2 , ..., 2 n " 2 , S"" 1

A a"" 1 , i, a 1 , ..., s n -3, 2 Q - 2

, , r n-1

to the generators of C, C, . .., L T -, , the vectors after the 2 th have always

n-2 n-1

the factor 2 in their subscripts and have any combination from 2 , 1, 2,

2 , ..., 2 in their subscripts. That is, all vectors after the 2 th from

^n-2 t0 ^gCn-D.-g ^ ^ V" 1 ^' 2 ^ ^ ^ ^ &1 ' "'" ^ ^

arranged in the new arrangement. The adjacent vectors

^2 n - 1 + f(2 n - 2 ,2 n " 3 , . . .,£) V^f (2 n " 2 ,2 n - 3 , . . .,2 1 ) + 1

in £ n , £, , ..., ^ TVT _-| (where f (2 I ,2 ,...,2 ) means that some combination

n-2 n-? 1
from 2 ,2 , ..., 2 is added) become respectively the adjacent vectors

V" 2 + f (2 n - 3 ,2 n "\ . . .,2,1)' V" 2 + f (2 n - 3 ,2 n "\ . ..,2 } ±) + 2 n - 1

after the substitution.

Therefore, this theorem holds.

-1*8-

Example 5 . 1

0, 1, 2, 3, h, 5, 6, 7 , 8, 9, 10, 11, 12, 13, H*, 15 ,
is rearranged to

0, 8, 1, 9, 2, 10, 3, 11, 1*, 12 , 3, 13 , 6, H* , 7, 13 ,
after the substitution.

Theorem 5-H-

r

N-2r N-r
s - s

dependent
A

V ^l

V

independent

N-r -r N-l
s k

When every £. for N-r - r < i < N - 1 is an independent vector of

1 S iC

L, £, , . .., ^t\t -i an< ^ the others are independent vectors of £_., C, ..., £,, -, ,

where r, > r > r. , let C T and £, T be expressed by
1 s k N-r N-r -r.

s s k

C T = a n ^ n + a, £ +a C + ... + a £ o (5-5)

N ' r s ° ° X r s 2 2-r s (2 ^_ 2) (2 s_ 2)r ^

s

(cf. Theorem 5 .7) and

L, = b n £- + 13,5 + b C + ... + b . r (5.6)

N " r " r k ° ° 1 r k 2 2-r N-r -2r, /r. N-r -2r

SK K K skKsk

(cf. Theorem 5.8). Then

a. | = 1 for any i (0 < i < (2 - s))

N-r - 2r

b. | = 1 for any i (0 < i < )

l — — r.

k

Proof. From the assumption of this theorem, £. for N-r -r<i<N-l

1 S K

is a dependent vector of ± , £., . .., £ . Therefore, of course, £ for

N-r < i < N - 1 is a dependent vector. Therefore, from Theorem 5-7> Eq. (5-5)
s — —

holds.

From Eq. (5-5),

( Vr } * ( Vr } = a oVs + a l^r *(N-r ) + "'
s s s s

accordingly,

^0 = a oVr + a l^r ©(N-r ) + '" (5 ' ?)

s s s

Substituting £ of Eq. (5-5) to Eq. (5-7),

s

2
C = a (a n L + a £ + . . „ } + a n £ /„ \ + .... = a C + a at +
000 1 r lr ©(N-r ) 1 r

s s s s

(a* - i)£ Q + a a^ r + ... = (5.8)

s

can be obtained,

In Eq. (5-8), the subscript of each £ in each term of Eq. (5-8) consists

of r , 2r , .... (2 S - l)r since i • r ©(N-r)<N-r for 1 < i < (2 S -2)r ,
s' s' ' s s s s - — s

Therefore, from the assumption, those £ are independent vectors of £_, £,, ...,
£ -. . Therefore, in order to let Eq. (5.8) hold, each coefficient must become
zero. Therefore,

a o = x

Similarly

a 2 - 1

1

-50-

can be obtained. And, similarly,

b 2 = i

1

can be obtained,

6. SOME PROPERTIES OF Z (CF. DEFINITION 3.6)
Suppose the following:

Condition 6.1 . The independent vectors of C, £-, , £ p , • ••> £ N -, are only i ,
i v ..., 5 (k . l} , 5 (k . l} , ..., £ (k . l} ; and 5 ± for any i ( 2 k " + £ + 1

2 2 +-L 2 +#

(k-l)
< i < N - l) is a dependent vector of £,_, i , ..., L -, , where < i < 2

Define V , V, , V_, . . . , V , , x as follows
1 2 (n-k;

V,

V.

tt Q ,

^k>

- (5

2-2

k'

S l'

& k '
2+1

3 k '
2-2+1

' £ k }
2-1

A

.., £

gCk+D.!

> (6.1)

.... 5

3-2 k -l

V 2 (n_k) -1 ' (C (2 (n - k) -l)2*' ^2 (n - k) -l)2 k ' "" ^^

Definition 6.1 . Z. (cf. Definition 3.7)

Define Z_, Z n , Z^, .... Z , , \ as follows
0' 1' 2' (2^-1)

12

.k'

k >

1-2+1

' k
(1+1)2-1

Z. =

1

k >

12+1

z k ,
\ 12 k ej

(i-2 +1)<

{(i+l)2 k -l}-

(1+1)2-1

k > "'

i2

Accordingly,

-51-

UNIVERSITY OF
ILLINOIS LIBRARY

■52-

Z =

V

V

z i' z 2' -' z (2 (^).x)

V Z3 ' "" W^-l)

Z iel> Z i»2' ••- ^(n-k)^.

(2^-1)' ""

Theorem 6.1 . Under Condition 6.1,

2 2

z o = z i

2 2

Z (2 (n " k) -1} := Vn Z °

z. • z. = — z.

1 J nTn 1(

holds, where of course < i, j < (2 -1} .

V_

Proof . Since the independent vectors of C, , L, . .., L are only in ,
under Condition 6.1,

T T

V V = V V =
11

• = V , , , V T , . v =2^
(2 (n-k)_ l} (2 (n-k)_ l}

(6.2)

can be obtained (cf. Eq. (3.16)).

The following relations hold clearly from Definition 3.5,
Definition 3.7 and Definition 6.1, that is,

-53-

I T

— v:v.

■± v T v. ,

-i v T v
Vn i ie2

^

1 T

= — v: ,v.

4 N le2 l

> (6.3)

IT IT

V n - k) -l} = Vn ViV ie{2 (n - k) -l} ^ Vn V ie{2 (n - k) -l} Vi

for any i (0 < i < 2^ n_k ' - l).

Therefore, from Eqs„ (6„3)>

Z 2 = — V T V n — V^V. = i V T V n V^V. = i V T (2 k E )V. (from Eq. (6.2))
l r i T i NiOOi N l x m ; i v ^ ^ ' '

k k

|- -A Z A (from Eqs. (6.3)) = y- Z Q

N

Therefore,

2 2

z o - z i =

= z ^).rl Zo

can be obtained. From Eqs. (6.3),

Z.Z.
1 J

IT IT ITT

^ l0 s[ N ° J N 1 j

i V T (2 k E )V. (from Eq. (6.2)
N 1 m j

2 k T
— V V
N i j

= ^r: n/n Z. . (from Eqs. (6.3)) = — Z.

can be obtained,

-54-

Theorem 6.2 . Under Condition 6.1, any V. for 1 < i < {2^ n_k ' - 1}
expressed by

can be

and

V. = V n A.
l l

v o = Vi>

V. = V.A.
l li

can be obtained where

A =

l

*j_y a 2 :

0'

(2 k -l)

(2 k -l)
le(2 k -l)

>(2 -1)

= U,

a

Oi

a

li

Q

2i

a

u

(2 k -l):

U k =

'I, 1

.1, -1

v

X

% 1

X . . . X

(The number of

.1, "I,

X i

.1, -1,

y

is k. )

Proof. Since every column vector, i.e., £ in V. is a dependent vector of £ ,

^1* "*f ^N-l frorri Condition 6.1, £ e V. can be expressed as a linear combina-

i2
tion of C, , £ , . .., C ,_ , i.e,

'0' =T

2 k -l'

^ k = a^ + a^ + . . . + a^ S^

(6.4)

Therefore,

-55-

(5 k ) « £j = (a C + a^ + ... + ^J^J ■ ^j

accordingly

^ k = a (vM + a Aei + ••• + a k ^ k ,

12 +j ° J X iej 2-1 (2-1 )®j

(6.5)

can be obtained for any j (0 < j < 2 - l), where the right-hand side of (6.5)

is a linear combination of £ , £ , . .., £ . Therefore,

° X 2-1

12* 12+1

12 +(2-1) ° 1

' 6 k }

2-1

l 0' <V

l 0'

a , . . . , a

* 2-1

le

(^-1)

Accordingly,

a , a , . . .,

2-1 2-2

V. = V_A.
1 1

(6.6)

can be obtained.

Applying Theorem 2.1 to A.,

A. = II A. II
1 k 1 k

can be obtained.

From Eq. (6.h),

«. 2k ) * ? 2 k ■ ^0 + a A + ••• + V-iW B V

Accordingly,

C . = a~£ , + a, 5 , + . . . + a .. £ . .
1 ° 2 k 1 2 k +l 2 k -l 2 k +(2 k -l)

-56-
can be obtained. Therefore, similarly,

^5i--W'VW""H ,ii

V Q = V.A. (6.7)

can be obtained. Therefore, from Eq. (6.6) and Eq. (6.7),

V. = V.A 2
l li

and

2
V = V A
i

can be obtained,

Theorem 6.3 . Under Condition 6.1, every V i for l<i< (2 ln -l) can be
expressed by

V. = V n A.
1 1

from Theorem 6.2. Then,

A. . = A. -A.

can be obtained,

Proof. oiiuv

-57-

^

V. = V n A.

1 1

V. = V n A. >

J J (

V. . = V n A. .

(6.8)

T T

V V = V V A.

i 00

T T

V V = V V A

can be obtained. Therefore, from Eqs. (6. 3),

"A

Z. = Z n A.
l l

Z. = Z.A.
J j

(6.9)

can be obtained. From Eqs. (6.9) and Theorem 6.1,

■s/k „ „ n/n

Vn

i.j 2 T z i z j " ^ ViV; " J \\\\\\\\\\^\

= -f U.A„ A.A.A- U. = -f U. AT A.A.U. = ■— Z^A.A. = Z_A.A.
.j^ n k k k ^ n 1 j k o k0ij Oij

2 1

(6.10)

where

Z = U k A Z Q U k

A. = U.A.U.
1 k 1 k

A. = U.A.U.
J k j k

T
V_V. .
lej

" v oVi A j

-58-

T

T
V V V A A

OOOi j

2^ V. . = 2^ V A. A. (from Eq. (6.2))
m lej m o l j

V. . = V_A.A.
iej i j

(6.11)

can be obtained. Then from Eq. (6.8) and Eq. (6.11), put

A. . = A. ' A.

Theorem G.h. Under Condition 6.1,

can be obtained, where

a. . = 1 or -1 or

V. = V Q A for any i (l < i < 2^"^ - l)

Q

Oi

A. = U,
i k

a

li

a

(2 k -l)i

Without loss of generality, put

a. . = 1 or -1

Accordingly,

2 2
A = A =
A l A 2

+ A'

{2 (n ' k) -l}

= E,

of. From Theorem 6.2,

Accordingly,

•59-

v o = Vi

T T
V V = V V A
i

Z " Z A i

(from Eqs. (6.3))

(6.12)

can be obtained,

Let Z-., A. be
0' 1

*\

z o = U k

u.

2 k -l

and

>

(6.13)

o:

Oi

A. = U.
1 k

a n .
li

u

a

2 k -l)i;

J

From (6.12) and (6.I3),

v. = v.a. .

v. (a.. - 1) =

(6.14)

■6o-

can "be obtained. From (6.14),

V. =

J

or a . . = 1

a. . = + 1

(6.15)

can be obtained.

Therefore, from Eq. (6.15) and the relation of Theorem 6.1, i.e.,

2 2 2 2

i'-^i^-u'Tx °

a.. = 1 can "be determined without loss of generality for any value of V.

Theorem 6.5 . The absolute value of characteristic values of Z. for any i

(0 < i < 2^ n_k ^ - 1) is equal to or —- .

VN

Proof . Applying Theorem 2.1 to Z ,

z o = \

u.

2 k -l

/

can be obtained.
Since

holds from Theorem 6.1,

2 2

z °^ z °

2 2
V. = — V.

1 4k x

can be obtained.

Therefore, since

v.(v. - z- ) = o

1 L s/N

v. = or V. = —

1 n/n

2 2

z o ■ z i ■ •

2 2^

= Z {2 (n - k) -l} = N/N Z °

holds from Theorem 6.1, the absolute value of characteristic values of Z. for

, i

Cn-k) ?

any i (0 < i < 2 V ' - l) is equal to or — .

VN

Theorem 6.6. When

/%

V. = V_A. = V U
J j Ok

a

1J

Q

(2 k -Dj

n-k

for any j (l < j < 2 - l) under Condition 6.1, if

(4 n) ) T

e v

and

V

I = S2 + i

j

holds, where < S < 2^ n ~ k ' - 1 and < i < (2 k - l),

•62-

(l^.a^-.a e(a ^ ) - (4 n " k) ) T

holds where

u = fu (n) u (n) J n) ) =-i (V n > a (n) e (n)> )

cf. Definition 3.5,

Proof. Since

(°)V e V

(4 B) )

I = S2 k + i

holds from the assumption

f| D) ) T =(W f). (4 n " k) ) T (6.16)

can clearly be obtained. Therefore,

v . (^

holds .

Let the ith row vector of V. be v.

J 1

Since

V. = V n A.

'1 ^S

can be obtained. Therefore, from Theorem 2.2,

/ (k)\T A / (k)Vr
v. = in. J A. = a. . I u. ' J

can be obtained. Therefore,

fu (n) \ T - ^u (k)T a u (k)T a u (k)T a u (k)
V U I ) ~ \^i ' a il u i > a i2 u i "•"' ^(n-k)^ u i

T

( (k) T (k) T (k) T \ , n
= u ,u. ,...,u. a (i,a.,,a. n , . . .,a , , \
\ i i i / ' il' i2' ' i(2^ n '^-1)

(6.17)

can be obtained. Therefore, from Eq (6.16) and Eq, (6.17),

il' i2' i(2^ ^-1'

(4 n " k) )

can be obtained.

Condition 6.2 . Suppose that there exists £. for a suitable i (0 < i < 2 - l)
corresponding to A. for any j (l < j < 2 - l) such that

J

CI

Oj

a

(k) _

lj

a

2j

a

(2 k -l)j

where

-6k-

A. = U,
J k

Q

Oj

\

a io °

a

2j

a

(2 k -l)j

(cf . Theorem 6.2).

Theorem 6.7 . Let A. be

a i' V •••' a , k

(2^-1)

«!,

A. =
J

a , a , . . ., a

J le(2 -1)

'*' ^' '•" ^(2 k -l)

(2 k -l)

• • • :. a Q

and

Under Condition 6.2,

a=a=...=a. ,=a. n =...=a . =0

o i i-i 1+ i (2 k_ 1}

a. = 1
l

can he obtained.

-65-

Proof . Ap] g Theorem 2.1 to A.

J

a - -±- (a a a )u (k) - -A- ^ (k) Vu (k) - fu (k) Y r u (k)

^ J° J 1 j(2
can be obtained. Therefore,

&n = 1 when £ = i
a.g = when £ ^ i

can be obtained,

Now, in the case of a group code, it is found below that Condition 6.1

and Condition 6.2 are satisfied.,

(n) T (n) T
In a group code, if there exist row vectors of V in ui. , u , ...,

( n ) J ■ ( n ) ( n ) ( n ) +^ ^ ^ 4- *

u / , N and xn u / , \, u / , \ , . .., u. T ' , the number of row vectors of
2 (n~l)_ 1 2 (n-l)' 2 (n-l) +1 ' TJ-1

(n) (n) ( n) *
V in ul , u, ..... u , , \ is equal to the number of row vectors of V
1 2^-1

. (n) T (n) T (n)' 1 '

inU 2 (n-l)> U 2 (n-1) + ^ — Vl ■ T

Similarly, in a group code, if there exist row vectors V in u^ ,

f \? ( > T " '■ \ T ( \ T f \ T

(n) \ n ) ^ • l n ) l n ) ( n )

\x: , .c., u . ana xn u , u , ..„, u , , \ , the number of row vectors

1 2-1 2 k 2+1 2 U j -l

( i ( i f >
of V in u. , v.: ..-.., u \ is equal to the number of row vectors of V
1 2 k_ x

(n) T (n^ T (n) T
in u . , u . , .... u /. , \ . Therefore, if there exist any independent

2 k 2 k +l 2 (k+l) -l

vectors of £ , L ,...,£ 'in £,£,..., £ , and in £ ,

U 1 W_1 £2 £2+1 (£+1)2-1 (£+1)2*

£ , , . .., £ , , the number of independent vectors of £_, C, „..,
(£+1)2+1 (£+2)2-1 ° X

E_ , in £ v ; 5 v j ..., 5 , is equal to the number of independent
W_1 i2 K £2+1 (£+1)2-1

vectors of C, t, „„„, C in £ , C ,...,£ fc .

U X W 1 (£+1)2* (£+1)2+1 (£+2)2-1

-66-

Therefore, since the total number of group codes is of the form 2 ,
if there exist independent vectors of £ , £ , . .., C in £ , £ , . .., £ ,

t ~

the number of independent vectors is of the form 2 (t < s). Therefore,

applying Theorem 5-10 a suitable number of times to £_, £, , . .., L and

renumbering the subscripts in natural order from the first vector, only £_, C ,

£„, . ... £ are independent vectors of £_, £, , .... C T .. and the others are
2 / s -, \ 1 N-l

dependent vectors of £~, £ , ..., £ -, . This is Condition 6.1.

Now, consider uj , u' , u t where
a b c

"N

I = S 2 + a
a a

K = S . 2S + * f

I = S 2 + c

C C y

(6.18)

and < S , S, , S < (2^ n_S ' ) - l), < a, b, c < (2 S - l]

3, D C

Assume that

b c

(6.19)

holds. (There always exists I such that I ©1=1 is a group code.)
Therefore, from Eq. (6.18) and Eq. (6.I9),

S 2 S + c = (S © Sj2 + (a © b)
c a b

• • o — o © o_
cab

"\

>

(6.20)

y

can be obtained.

Applying The ore i: 6.1 bo Eq. 6.20,

.(n-s) < p(n-s) _ ^(n-s) m ^(n-s)

'S ®S, S
a b a

(6.21)

can be obtained.

Now, ui ' € V can be assumed without, loss of generality. Therefore,
Eq. (6.21) means that Condition 6.2 is satisfied.

Remark 6.1 . In the case that Condition 6,1 and Condition 6.2 are satisfied but
the code is not a group code,

cab

is satisfied but

holds (cf. Eq. (6.20)

Remark 6,2. When V satisifes Condition 6,1 and Condition 6.2, and

%

a

(k) =
i

lj

:t

2j

a

(2 k -i)j

holds (cf. Condition 6.2),

[a 0J ,a lri ,a 2J ,...,a }

-68-

becomes an Abelian group under the operation of multiplication. Accordingly,
considering the matrix a

1, X,

1,

1, ..., 1

a =

1, a 1±f a ±2 ,

1> ^l' Q 22'

a iV '••' a n-k)
13 l(2 n kj -l)

Q

a

S3' ••" 2(2^).^

l, a k , a k

(2-1)1 (2-1)2

. . ., a

*-i)(2 (n - k) -i)

(as u^ e V can be assumed without loss of generality, it may follow that

01 02

that

= a

o( 2 (n - k) -i:

= l) there exist i_, i , . .., i / , \ such

(2'

•)

,(k) (k) (k) (k)

1 2 {2 ( n - k) -l}

from Condition 6.2.

From Theorem 6.6 and Condition 6.2, Ct is reduced to the following
form:

a

(n-k)
'0

(n-k)

T

(n-k)

T

(6.22)

-6 9 -

Since {1,Q. .,&,..„,., a ) is an Abelian group as mi i<;d abo

U 2j (2 k_ i} .

f, (n-k) (n-k)

p(n-k)

" S k
2-1

becomes an Abelian group under the operation "h 1

7. SOLUTION OF EQ. (3=25) "VA'V T = 0" UNDER CONDITION 6.1 and CONDITION 6.2
Even if generators of £ n , £,, , .., £ , are rearranged in any order,

m

Eq. (3-25), i.e., VA'V" 1 " = 0, holds. Let the transformation of the rearrangement
of generators of £ n , £, , . „., C be t, that is,

V'T = W

From Theorem 4.U, A' is invariant under the transformation, i.e.,

tA*t T = A'

Therefore,

WA*W T = VTA'T T V T = VA'V T = (7.1)

can be obtained.

T
Since it is clear that A. = A. holds from Theorem 6„3>

11

VA>V T = (V ,V A 1 ,V A e ,...,V oA(2(n . k) ^ i )A-(y o ,V A 1 ,.„. ) V A [2(n _ k) ^) T

" V A + VA + V2 A 2 + -• + A (2 (^). 1) A [2 (n-k). 1 , A {2 (n- k )_ 1) > V " °

Accordingly,

V (A + A AAl + A 2V2 + ... + \ 2 (n-*)_ 1) \ 2 (n-K)_ 1) \ 2 (n-K)_ 1] »0

)V* =

(7.2)

can be obtained, where

-70-

where

A)

A,

A' a

A

2 (n " k) -l}

Considering Theorem 6.7, let A. for any j (l < j < 2 - l) be

V V ••" a 2 k_ x

> (7A)

a o ~ a i

a , , . „ . , a
2-1 °

i.-l i.+l n k ,
J J 2-1

a. = 1
i .
J

J

< i. < 2 - 1
- J -

(7 = 5)

Since

\'

J2

A.
J

X ' k
J2%1

X ' k k
J2 +2-1

holds from Eq. (7=3),

-72-

V k
J2 +i.

A.'

A.A.A. =
J J

J

(7.6)

\'

[j2 k + i? k -l)©i

can be obtained from Eq„ (7°*0
Therefore, let

A n + AAA + ... + A f x A / . v A , . x
1 1 ( 2 (n - k) -l) {2 (n - k) -l} {2 (n - k) -l}

The following relations can be obtained:

(2 k -l)
(7,7)

° ° 2 k + i x 2.2 k + i 2 3 '2 k + i 3

+ ... + \'

In general,

(2 (n-k)_ 1)2 k + .

>

i2 (n - k) -l}

v . = \ \ + \ ' + ^'v + . . . + \ • / . * . y

3 2%(jei ) 2 <2 k + (jei) {2 (n - kj -l)2 k + { jei , . , }

^ {2 U_k; -l}

where

< j < (2 K - 1)

y

(7.8)

-73-

Now, the solution such that the number of most efficient codes if;
is discussed below.

Theorem 7.1 . In Eq. (7-8), when V Q = 0,

(7.9)

V. =
J

can be obtained for any j (0 < j < (2 -l))

Proof. Applying the result of Theorem 3.1 to Eq. (7-8),

in) (n) (n)

(h^h i; . ..^(u + ay 4- ... + a ,

+1 1 t2 - 1>Z +X i2 ("-*). 1}

can be obtained, where h' = h - 1 = 0.
Since

(k) (k) (k)

1 Cg^^-l]

is an Abelian group from Remark 6.2 whose generators (i.e., bases of the
Abelian group) are |< k > , (« |W l« ... tj^j,

u ° > +il + - + V n - k) -i^ + i , >, (7ao)

. (n) + u ( "> V /(n) \ /(n) (n)

(n)

(n-k-1)

d +1 fn.lr.l ,

-7k-

can be obtained.

Since u' n is the column vector of U , the elements of (u^ + u^
x n \ i

are or 2, I.e., non-negative in general. Therefore, letting

P \

the right-hand side of Eq„ (7.10)

\ X N-1 /

(7.11)

x. >
l —

(7.12)

can be obtained for any i(0<i<(N-l))
From Eq. (7.9) and Eq. (7.H),

V Q = (h',!^.,,,!^)

"N-l,

= Vo + h l X l + ••• + Vl X N-l (7 ° 13)

can be obtained.

Therefore, when V = holds,

h. =

1

rhen x. f

1 '

can be obtained from Definition 3.2, Eqs. (3. 5) and (7.12)
Now, from Eq. (7.8),

(7.14)

V i = X \ + A 'k + '•• + X ' (n-k) k

2 'N(jei L )

{2 (n ~ k) -l}

= (h',^,...,^) u +

(n) „(n)

+ „ „ . + u

2 +(jei 1 )

(n)

(2 (n - k) -l}2 k + Uei )

(2 U kj -l]

= (h^,...,^)

(n)

u + u + .,

2 K± 1

+ u

{2 (n-k)_ 1)2 k + .

» u

(n)

[2 (n-k)_

(h^,...,!^)

/ X ° \

(n)

u .
J

X

N-l

(from Eq. 7.10) and Eq. (7.11)

X U 0j

= (h^h^^h^;

x,u, .
1 lj

X N-l U (W-l)j

h X U 0j + h l X l U lj + -° + Vl) X (N-l) U (N-l)j

= (from Eq. (7.14))

can "be obtained,

Now, in the solution of VA'V = such that the number of most efficient

codes is 2 ,

det V Q £

can be obtained- Therefore, from Eq. (7.2),

A + A 1 A 1 A 1 + A 2 A 2 A 2 + '

-76-

A {2 (n - k) -l} A {2 (n - k) -l} A (2 (n - k) .~l}

=

can be obtained. Therefore, from Eq. (7.15) and Eq„ {7.7),

(7.15)

(2 k -l)

(7.16)

can be obtained.

Therefore, the problem can be reduced to that of obtaining maximum k
such that Eq, (7.l6) holds, Accordingly, from Theorem 7.1 the problem can be
reduced to that of obtaining maximum k such that V = 0.

Theorem 7-2 . The problem of obtaining maximum k such that V = can be reduced
to obtaining a solution in non-negative integers x, , x , . .., x , k, for the

equations

\„ + x, X' + x„\

1 r 1 2 (r 1 +r g )

. + x \, \

n ( r, +r^+„ . „+r )
12 n

(7.17)

1 + x n + x^ + „ . „ + x =2
12 n

(n-k)

(7.18)

which maximizes k where

-77-

(I) when k > (n - k)

1 - n-k 1

1 2 - n-k 1 n-k 2

X l + X 2 +

+ x , < , C i + i C o +
n-k — n-k 1 n-k 2

x, + x„ + . . . + x . . < 2
1 2 n-k+1 -

(n-k) _

x

(n-k) +

+ x < . C n

n — n-k n-k

^

+ vC > - 2 (n " k) - :

n-k n-k

o( n -k) -,
X] _ + x 2 + . . . + x k+1 < 2 - 1

x + x + ... + x. . + x, _ < . C + C_ + . .. + C .

2 3 k+1 k+2 - n-k 2 n-k 3 n-k n-k

x, + ... +x. . +x, , < ,C. + , C, + . „ „ + C .

3 k+2 k+3 - n-k 3 n-k k n-k n-k

> (7.19)

J

■78-

(II) when k < (n - k)

1 — n-k 1

x, + x_ < .C. + C_

1 2 — n-k 1 n-k 2

x. + x + x_ < C. + ,C. + . C_

1 2 3 ~~ n-k 1 n-k 2 n-k 3

X l + X 2 +

+ x. , < . C n + .C. +

k+1 — n-k 1 n-k 2

+ n-k C k+l

X 2 +

+ x. , + x. _ < . C + , CL + . . . + , C. _

k+1 k+2 - n-k 2 n-k 3 n-k k+2

x 3 +

+ x. _ < . C_ + . . o + , C. _
k+3 _ n-k 3 n ~k k+3

x _. + . . . + x . < . C _.+...+ ,C

n-2k n-k — n-k n-2k n-k n-k

n-2k+l n-k+1 — n-k n-2k+l n-k n-k

^

V

(7.20)

x ,+...+ x < ,C .

n-k n — n-k n-k

J

and where

and

r\= 2 , r_ = 2 , . . . , r , = 2 , r =1

1 '2 n-1 n

:, f x , ..., x are non-negative integers

Remark 7.1. Equation (7-17) is an indefinite equation of n variables (x v x ,

1' 2 ;

.... x ) of the first order. Therefore, the general solution can be always
7 n

i:ied. First, obtain a bo1u1 ion for maximum k L] tie general solution bui
that Eq. (7«l8) is satisfied. Then the conditions, i.e., k>n-kork<n-k
are determined. Next, investigate whether the solution satisfies Eq. (7.19)
or Eq. (7.20) corresponding to the conditions k > n - k or k < n - k, respectively.
If the solution does not satisfy Eq. (7. 19) or Eq. (7=20), obtain the solution
about the next maximum k in the general solution such that Eq. (7»l8) is
satisfied.

Continuing the precedure, the solution for maximum k such that
Eq. (7ol8) and Eq. (7. 19) or Eq. (7.20) are satisfied, can be obtained.
This is the desired solution.

Proof of Theorem 7.2 . In V (cf. Eq. (7-8)), since < ± ± < 2 - 1 (cf.

Eq. (7°5))> there exists a possibility that A' = A' or A' , or . ,.,

2 +i 1 r l r l +r 2

or A (cf. Theorem 4.4). A similar possibility exists with respect

r +r +. . .+r
r l 2 k+1

to X ,, , \ , A' / \ ,„..,A'/ \ . Therefore, the number of

(,K+±J [k+d) (,n-±J .

2 +1 2 2 +1 2 2 2 +1 2 (n-k-l)

A' having the possibility is , C, .

n-k 1

Next, there exists a possibility that A' = A or A'

3'2 k + i r l +r 2 r l +r 2 +r 3

3

or .... or V A similar possibility exists with respect to

r +r +„ . . +r
1 2 k+2

A' , A , ..,, and the number of A 1 which has the possibility is C
1- r^k . /■ „k . n-k 2

6-2 +i 6

Continuing the discussion, Fig. 7=1 and Fig. 7.2 can be obtained

5-2 +i c 6-2 +l c
5 o

corresponding to k > n - k and k < n - k, respectively.

In Fig. 7.1 and Fig. 7.2, (i) and (i)2 + j mean, respectively,

A' and A' ,

r, +r +. . .+r . / ^k .

12 1 (r +r +. . . +r. J 2 +j

As shown clearly in Fig. 7.1 and Fig. 7.2, the conditions (7.19) and
(7.20) can be obtained corresponding to k > n - k and k < n - k, respectively.
Equation* (7.17) is also satisfied.

-80-

, , k (D(2)(3)

(1)2* + i

(2)2 k + i
(3)2 k + i

(n-k)2 K + i

X l X 2 x 3

"n-k

L k+1

Figure 7.1. (k > (n - k))

(1)2 K + i
(2)2 k + i
(3)2 k + i

(1)(2)(3) (n-2k) (k) (k+1) (n-k)(n-k+l

(n)

(k + l)2 K + i

(n- k)2* + i

Figure 7-2. (k < (n - k))

-81-

Since the number of terms of the right-hand side of Eq. (7*8)
2 (n-kJ^ it is ciear that Eq> (7.i8) must hold.

Now, suppose that maximum k and x , x , „ . . , x such that Eq. (7.17)*
Eq. (7.18) and Eq. (7.19) or Eq. (7-20) are satisfied, have been obtained.
From Eq. (7.19) and Eq, (7/20),

x n < . C,

1 - n-k 1

holds. Therefore, x, of the elements \\ , X ' . , X\ _. ,...,

1 o k • o k+1 • n k+2 •

2 +i, 2 +i 2 +i

2

\' / , \ , can take the value \' . It is quite arbitrary which of them

2 (n-k-l)

take the value A,' .
r l
Therefore, let x, of them take the value A,' .
1 r l

Next, let x of the others whose number is ( , C, - x, ) and \' , ,

(— n— K -L -L A

3°2 +i

A.' , . . . , in general A, 1 , take the value A' . Since
5°2 +i (2)2+1 r l +r 2

x, + x_ < , C. + C_

1 2 — n-k 1 n-k 2

holds from Eq. (7.19) & n( 3- Eq. (7.20), the procedure is always possible.

Continuing such a procedure (it is always possible since Eq. (7.19)
and Eq. (7.20) hold corresponding to k > n - k and k < n - k, respectively and
Eq. (7.18) holds), the value of each term of the right-hand side of Eq. (7.8)
can be determined and V = holds from Eq. (7.17) ° Then, of course, i, , i ,

V

., can also be determined,

Remark 7 » 2 . The values of i, , i , ..., can be determined as shown in the proof
of Theorem 7.2.
Since

-82-

V n = V.A.
J J

holds for any j (0 < j < 2^'^ - l) from Eq. (6.7),

C = C = C
° V.i. J £ * + i.

J J

(7.21)

can be obtained from Theorem 6.7,

Therefore, from Eq. (7.21)

^

JS +(i.el)

J

2 k

J2%(i ®2)

J

>

2 k -l j2 k +{i e(2 k -l)}

(7.22)

can be obtained. Therefore,

j2 +i.

J

= z

j2 +(i e2)

J

1

Z =7

2 k -l j2 k +{i.e(2 k -l)j
J J

(7.23)

can be obtained.

Now, from Theorem 3.1 and Eq. (3.27),

-83-

ZA'Z = U

U A'U

n n

vj

u

k N-l

/ X

= u

(H(n,p) - E N )

k N-l

x

N-l

U

=

Accordingly,

/ x.

(H(n,p) - E N )

U-l

=

(7.24)

Hf-1

can be obtained „

.(n)

T

Equation (7.24) means that when x. is identically zero, u^ 11 £ V

(n) T ""

and when x. is not identically zero, u. e V,
l i

On the other hand, applying (Theorem 2.1) to Z,

x. =>Tw (vv-" z N-i )u i

(n)

(7.25)

can be obtained, for any i(0<i<N-l).

Therefore, it is possible from Eq (7.23) and Eq. (7.25) to find

.(n)

such that

■8k-

u. n) £ V. when x. £
11 l r

u' n ^ jt V. when x. =
1 i i J

(7.26)

Therefore, all the codes corresponding to the binary expression of i such that
x i ^ are the set of most efficient codes under the conditions.

Remark 7.3 . In general, 2 < the number of most efficient codes < 2 n_P+1 holds
(cf. Y. Komamiya: Bulletin of Electrotechnical Laboratory, Vol. 17, pp 298-3IO,
1953 and Proceedings of the Third Japan National Congress for Applied Mechanics,
195*0- Therefore, letting K Q be a maximum k,

1 5 K 5 n - P + ! (7*27)

can be obtained.

Remark 7.4 . When there exist A , A , ..., A , v satisfying Eq. (7.15),

d (2 ln " iJ -l)

+ A , + A .., + A , x also clearly satisfy Eq. (7.15).
2 {2 ln ~ RJ -l)

Example 7.1 . The case of n = 3, p = 2.

From Theorem k-.k and Theorem 4.6,

\>-

k

A.

r l

2

X
r i +r 2

\

r 1+ r 2+ r 3

-2

•85-

Accordingly,

"\

*0" 3

\' = 1

T +T

12

r l +r 2 +r 3

= -1

= -3

(7.28)

J

*0-3

K =X 2 =X h =1

3 5 6

V" 3

(7.29)

can "be obtained.

Applying Theorem 7-2 to this case,

>v

3 + x 1 - x 2 - 3* 3 =

1 + x, + x + x_ = 2

J

(7.30)

From Eq. (7-27),

k<n-p + l=3-2 + l = 2

can be obtained.

Now, let k be 2, i.e.,

■86-

k = 2

(7-31)

Therefore, from Eq. (7-31) and Eqs. (7. 30),

X l " x 2 " 3x 3 + 3 = °

-\

X l + X 2 + x 3 " X = (

x 3 = l

X l = x 2 ■ " °

can be obtained. From Eq. (7.31),

k = 2>n-k=3-2 = l

(7.32)

k > n - k

(7.33)

can be obtained.

It is shown below that Eqs. (7.32) satisfy Eqs. (7.I9)

X l =

X-, =

X l + X 2

X l + X 2 + x 3
x 1 + x 2 + x 3

°-S c i

< 2 n ' k -1=2

< 2' -1=1

1 < 2' -1 = 1

1 5 i c i " x

"\

-1 = 1

J

Therefore, since

t2 (n " k) -l) X

4 = 3

(7.3i*)

-87-

can be obtained. Therefore, from (7-23)>

z = Z 7

-\

Accordingly,

z l " z 6

\* z 5

Z_ = Z,
3 ^ J

X

(7-35)

can be obtained. Therefore, from Eqs. (7-35) and Eq„ (7.25),

x = V8

x, = -f~8

x £ = ^8

x -^8

x, = -Jq

x = ^8

= ^8

X 7 =

z Q + z x + z 2 + ... + z ) = 2vT8 (z Q + z 1 + z 2 + z ) ^

z " z l + z 2 ' z 3 + z 4 " z 5 + z 6 " z 7 } = °

z + z l ' z 2 " z 3 + \ + z 5 " Z 6 " z 7 } = °

z " z l " z 2 + z 3 + z 4 ' z 5 " z 6 + z 7 } = ^ (z ' z l " z 2 + z 3 } ^ °

z + z l + z 2 + z 3 - \ - z 5 ' z 6 " z 7 } = °

z " z l + z 2 " z 3 " \ + z 5 " z 6 + z 7^ = ( z - z x + z 2 - z^) ^
z + z l " z 2 - z 3 " \ - z 5 + z 6 + z 7 } = ^ 8 U + z l " z 2 " z 3 } ^ °

z " z l ' z 2 + z 3 " \ + z 5 + z 6 ' z 7 } = °

can be obtained. Therefore, x n ^ 0, x ^ 0, x ^ 0, x-r ^ can be obtained,
Therefore, the most efficient codes are

-88-

[°

1

1

1

1

1

1

(7=36)

Example 7*2 . The case n = 3> P = 3

From Theorem k.h and Theorem h.6,

K^6

\

r.

r +r
12

A.'
r +r +r
12 3

=

>

=

J

(7.37)

can be obtained „ From Eq. (7-27),

1 <k< 3 - 3 + 1 = 1

can be obtained. Therefore, in this case, k = 1 can be obtained.
Applying Theorem 7.2 to this case,

6 + x 1 * + x (-2) + x • =

1 + x + x + x = 2 = ^+
J- <- j

x l " x 3 " °

x 3 = 3

"\

(7.38)

(7.39)

can be obtained.

-8

Since n-k=3-l = 2 and k = 1 hold, k < n - k can be obtained.
It is clear that Eq. (7-39) satisfies Eq. (7.20).
From Eq. (7-8)

1 2 +i 2 J 3

can be obtained. Therefore, from Eq. (7. 39) t

\

2 + i 1 = 3

2 + i 2 = 5 >

3-2 + i = 6j

Accordingly,

•i- 1

Si" 1

i 3 = o

can be obtained. Therefore, from Eq. (7.23),

z o = z 3 = z 5 = Z 6

z l = z 2 = z 4 = z 7

(7.1*0)

can be obtained.

Therefore, from Eqs. (7.U0) and Eq. (7.25),

■90-

x ^0

x ? f

"\

\

x l = x 2 = x 3 = \ = x 5 = x 6 = ° .

(7A1)

can be obtained. Therefore, the most efficient codes of this case are

'0

a i i,

(l.h2)

8. GENERAL SOLUTION OF VA'V T =

Since

Z = -i (1,1,. ..,1)6

VN

(8.1)

holds from Definition 3-6,

(n)

.(n) 1

= vN (z_, z, , . . ., z_ T n )u. = 1 when uY

Cr 1 N-l i l

:. -Vm (z ,z 1 ,...,z n _ 1 )u^ = when u[ n) ft V

> (8.1')

v

can be obtained, where

/ x r

Z = U

u

x

N-l

(cf. Definition 3.7). Therefore,

x Q = x ± + . . . + x = m

(8.2)

can be obtained where m is the greatest possible number of most efficient codes
Since

z ^(i,i,...,iK ,

z o =

m
n/n

(8.3)

can be obtained.

-91-

-92-

Now, the discussion from Eq. (7-24) to Eq. (7.26) holds in general.

Therefore, letting the number of x. such that x. - be a,
7 ° l l

m = N - a (8.4)

can be obtained.

Since each z. for any i (0 < i < N - l) can be expressed as a linear
combination of x fi , x-,, . .., x , from Eq. (8.1), "a" elements of z , z,, . ..,

z can be considered the independent variables.

From Eq. (8.4), in order to let m be a maximum, it is necessary to
let a be a minimum, that is,

max(m) = N - min(a) (8.5)

Now, let the relation among z , z , ..., z obtained from Eq. (3«27)>
i.e., ZA'Z = be

R or R or R or ... (8.6)

If the relation in which the number of independent variables among
z , z , z , ,.., z is a minimum is selected among the relations R , R ,
R , ..., the number is max(N - a), i.e., max(m).

Example 8.1 . The case n = 3> p = 2

This case is Example 7-L Here, the case will be solved by the
method developed in this section.

From Eq. (7.29),

-93-

s>

' 3

\

X i = K " K ■ x

S " S " ^ " - 1

>•

*} - -3 _

holds. Therefore, from the equation ZA'Z = 0,

Vl " Z 6 Z 7

z o z 2 = Z 5 Z 7

<

Z Z 3 = \ z l + Z 5 Z 6 ' z l z 2

Z Z 4 " Z 3 Z 7

Z Z 5 " Z 2 Z 7 + Z 3 Z 6 " z l z 4

Z Z 6 = z l z 7 + Z 3 Z 5 " Vk

r

z l z 3 = V<

< z l z 5 = Z 2 Z 6

v.

Z 2 Z 3 = V 5

(8.7)
(8.8)

(8.9)

(8.10)

(8.11)

(8.12)

(8.13)

(8.14)

(8.15)

. 9 k-

r

3( Z ;

2, 2 2 2

Zy) + z i + z 2 "

It

f 2 2 2, .

^ z 3 + z 5 + z 6 ) =

3(z

2x 2 2 2

" z ^ - z 3 + z^

1 " V + z o

<

^/ 2 2x 2 2 2

3(z 2 - z 5 ) + z 3 + z Q + z 6

,2 2 2v

^ Z 2 + \ + v

(2 2 2,

(z l + z 7 + V

v

nt 2 2v 2 2 2/2 2 2-.

3(z 3 - z^) + z 2 + z x + z - (z Q + Zg + z J =

(8.16)

= (8.17)

= (8.18)

(8.19:

can be obtained,

Substituting (8.7), (8.8), (8.10) in (8.9),

(1 -

#<v 3

v<

=

(8.20)

can be obtained, Similarly, substituting (8.7), (8.8), (8. 10) in (8. 11) and
(8.12),

(1

~I )(z z 5
z o

z 3 z 6 ) =

(8.21)

(1

z o

z 3 z 5 )

=

(8.22)

respectively can be obtained.

From (8.20), (8.21) and (8.22),

/r s 2 2

(I) z ? = Z Q

I

I

V 3 = Z 5 Z 6

Z Z 5 = Z 3 Z 6

^ Z Z 6 = Z 3 Z 5

(8.

(8.2*0

(8.25)

can be obtained.

From (II),

3 2 2 2

V 3 Z 5 Z 6 = Z 3 Z 5 Z 6

Z 3 Z 5 Z 6 (z 3 Z 5 Z 6 ' z }

=

can be obtained, Therefore,

ll. l) ^5 Z 6 =

or

(II. 2) z^z

6 = Z

can be obtained,

In (11,1), when z = 0, from (8.24), (8.25),

z 5 = z 6 = °

can be obtained. Similarly whe z,_ =0, z^ = z r = can be obtained, and when

5 3°

z^ =0, z = z = 0, Therefore, when (ll.l),

z 3 = z 5 = z 6 = °

(8.26)

can be obtained. Therefore, from (8.7), (8.8) and (8.9),

-96-

z l = z 2 = \ = ° (8=27)

can be obtained. Therefore, from (8.16),

2 2
Z 7 = Z

can be obtained. Therefore, (II. l) can be reduced to (i).

Therefore, only the cases (l) and (11.2) may be analyzed,

(i) The case z_ = z

holds.

(1.1) When z ? = z Q

Z 7 = ± Z

z l = z 6 (8-28)

z 2 = z 5 (8.29)

\ = z 3 (8.30)

can be obtained. These relations, i.e., z ? = z Q , (8.28), (8.29), (8.3O) clearly
satisfy the relation (8.13) to (8.19). Therefore, in this case, the number of
independent variables among z Q , z ± , . .., z is 4. Therefore, the greatest
possible number, i.e., max(m) = k can be obtained.

As in Example 7.1, using the relations z = z , (8.28), (8.29), (8.3O)
to

*j =^N (z , Zl ,...,z 7 )u.
x = lf x 3 = 1 ' x 5 = 1 ' x 6 = ^ x i = x 2 = x 4 = x 7 = °

can be obtained. Therefore, the most efficient codes are

JO \

1

1

1

1

1

1

(1.2) z ? = -z Q

From (8.7), (8.8), (8.10),

z l = " z 6

^

Z 2 = " z 5 >

\ = " z 3

J

(8.31)

can be obtained. These relations, including z_ = -z , clearly satisfy the
relations from (8.13) to (8.19). Therefore, in this case, the number of
independent variables among z , z , ..., z 7 is h. Therefore, the greatest
possible number, i.e.,

max(m) = h

can be obtained.

From z = -z and (8.31), similarly

x l ~ x 2 ~ x k ~ x 7 " - 1

x,-, — x~ ■• X,- —■ X/- ~" u

0356

can be obtained. Therefore, the most efficient codes are

-98-

1

1

1

1

1

1

(II. 2) The case z z n z A =

3 5°

From z z z^ = z n and (8.23),

3=3
Z Z 3 " z o

3 2
Z 3 = Z

C" Z = ~f> (Cf. Eq. (8.3)))

(8.32)

can be obtained. Similarly (8,24) and (8.25),

2 2 2 2
Z 3 = z 5 = z 6 = z o

(8.33)

can be obtained.

On the other hand, from z^z^z A = z^ > ( ' . * z„ = — > 0)

3 5 6 ^

z >

\

"\

z 3 >0

z 6 >0 y

z r < .
6 y

*\

z 3 <0

. > y or z,_ < r or z._ > Y

5 [ 5 1 5

z r <
6 ^

>

V

z < o ;

z g >0

y

must hold. Therefore,

z 3 = z 5 = Z 6 = z

or

■"•'-

z 3 = " z 5 = z 6 = z

or

" z 3 = Z 5 = " z 6 = z

or

" z 3 = " z 5 = z 6 = z

can be obtained.

Therefore, from (8„7)> (8.8), (8.9) and the above relations,

or

or

or

Z l " z 2 " \ ~ T r Z 3 " Z 5 " Z 6 " Z

Z l " Z 2 " ~\ ~ ~ Z T Z 3 " " Z 5 " " z 6 " Z

" z l = Z 2 = -\ = V " Z 3 = Z 5 = " Z 6 = Z

z, = -z^ = -z, = z„, -z„ = -z r = Z A = z

1 - * 2 " h " "7' 3 ' 5 " 6 " "0

can be obtained. These relations also satisfy the relations from (8.I3) to
(8.I9). Therefore, in these cases, the number of independent variables amon£
z , z , . . . , z is 2. Therefore, the greatest possible number, i.e.^

max(m) = 2

can be obtained.

-100-

Calculating x ± = VN (z Q , z^ . . . ,z )u. by using these relations, the
following results can be obtained:

o\ /l \ /0 1 0\ / 1
i i i/, \0 1 1 / , \l 1/ , \ 1 1

Finally, max(m) = 4, the greatest possible number, that is (i.l) and
(1.2), can be obtained.

9. GENERAL SOLUTION OF VA'V T = IN APPLICATION OF BOOLEAN ALGEfc

T
A necessary and sufficient condition that VA'V = is that

x.x.h. . = (9.1)

i J i®J

when i ^ j (0 < i, j <* 2 n - l), and that x 2 h' = for < i < 2 U - 1.

2
Equation (9.1) follows from Eq. (7.24), and x.h' = because h' = 0,

Since x. = 1 or holds for any i(0<i<2 n -l) from Eq, (8.1 1 ),

x. can be considered as a variable of a Boolean function.

l

In order to satisfy Eq. (9.1). when h. . = 1, x.x. = must hold, but

lej ' l j

when h. . = 0, the value of x.x. may be arbitrary.

Therefore, when h. . = 1.
lej

x ± x. = (9,2)

.'. 7, v y . = 1 (9-3)

J

must hold for any i / j (0 < i, j < 2 - l), where y. is a negation of x.,

"N

y. = x:

^i i

> (9.4)

y. = x

J

Therefore,

0<i

,j<£ n -

-l

n

(*i

\s

V

= 1

h.
i

.=i

(9.5)

-101-

-102-

must hold. Therefore, after the expansion of Eq. (9»5)> choose the term whose
number of variables (y.'s) is minimal.
Now, suppose that the term is

y, y, ...y, (9.6)

Then if

y, y, ...y, - i (9-7)

X l X 2 ^

holds,

y, - y, = ... = y. = l (9.8)

x i x 2 ± i

can be obtained. Therefore, from Eq. {9 .h) and Eq. (9-8),

x. = x. = ... = x. =0 (9.9)

X l X 2 H

can be obtained. This means that ifx. =x. = ... = x. =0,

X l X 2 H

VA'V T =

can be obtained, where I is the minimum number of Boolean variables among terms
in the expansion of Eq. (9.5) whose Boolean variables are equal to zero.
Therefore, put x. = 1 for any i (0 < i < 2 -l), where

i / \> i t i- 2 ' '"' i ^ ± £

Then, the greatest possible number of most efficient codes is

(N - £) (9.10)

-103-

and the most efficient codes consist of the binary codes corresponding to a;

(0 < i < 2 n - 1) for 1 / i,, i / i oJP ..., i /

V

Remark 9 ■ 1 - Without loss of generality, u € V can be assumed. Therefore,

x. = 1 can be assumed,

Example \$.1 . The case n = 3> P = 2
From Example 3»3.>

h' = 0, b. = h = h, = 1, h = h = h. = h =

l " 2 "' 1* "' ' 3 5 "" 6 "' 7

can be obtained. Therefore, from Eq„ (9*2)

X X 1

X X 2

x o x u

X 1 X 3

X 1 X 5

X 2 X 3

X 2 X 6

X 3 X 7

x h x 5

x k x 6

X 5 X 7

= o ^

=

=

=

=

=

=

=

=

=

=

>

(9.11)

x 6 x ? = J

-101+-

can be obtained. From Remark 9.1,

(9-12)

*o = 1

holds without loss of generality. Therefore, from Eq. (9«5)>

y 1 y 2 y i+ (y 1 v yJ(y x v y^)(y 2 v y 3 )(y 2 v ygKy^ v y )
• (y^ v y 5 )(y J+ v y^)(y 5 ^ y 7^ y 6 v y 7^ = 1

can be obtained. Therefore,

Eq. (9 = 12) = y 1 y 2 y i ^(y 1 v y^Hyg v y 3 y 6 )(y 3 v y^)(y J+ v y^Ky y 6 v y^)

= y 1 y 2 y 1+ (i v y^H 1 ^ y^)^ ^ y^)(i v y 5 y 6 )(y^y 6 v y ? )

= y 1 y 2 y i ^(y 3 v y 7 )(y 5 y 6 v y^)

= y 1 y 2 y i+ (y 3 y 5 y 6 v y ? )

= y 1 y 2 y i ^y 7 v y^ 2 y y f h y 3 v G (9.13)

The term of the right-hand side of Eq. (9.I3) whose number of
variables is minimal is

y ]_ y 2 y 4 y 7

Therefore, the greatest possible number of most efficient codes is 2 - k = h.
Therefore,

y 1 y 2 y i+ y ? = i

can be obtained. Therefore,

-105-

x l_ = x 2 = \ = X Y " °

Accordingly,

x " x 3 " x 5 " x 6 " 1

can be obtained. Therefore, the most efficient codes are

°

1

1

1

1

ll

1

10. CONCLUSION

Most efficient codes were found in principle by the methods discussed

above .

Now, define m , m , m as follows:
GOO

m : the number of most efficient group codes
G

m : the number of most efficient codes under Condition 6.1 and Condition 6.2
m : the number of most efficient codes in general

From the description of Section 7 and Remark 7° 3*

2 < m_ < m_ < m_ < 2 n_P+1 (10. l)

G L (J

can be obtained.

As a future problem, do there exist most efficient codes under

Condition 6„1 and Condition 6.2 such that m > m_? Another problem is to

G

obtain an elegant method of solution for general most efficient codes such that

m o > V

This paper has presented a new conclusion, that the most efficient
codes problem under Condition 6.1 and Condition 6.2 including group codes has
been solved completely.

-106-

1/

M 2 a tm

```